/*
 * Range represents a field in a string.
 */
package parser;

import java.util.*;

public class Range implements Comparable<Range> {
	private int begin, end;
	
	public Range(int begin, int end) throws RangeException {
		if(begin > end)
			throw new RangeException(begin, end);
		this.begin = begin;
		this.setEnd(end);
	}
	
	@Override
	public String toString() {
		return String.format("(%d, %d)", begin, end);
	}
	
	public void setBegin(int begin) {
		this.begin = begin;
	}
	
	public int getBegin() {
		return this.begin;
	}

	public void setEnd(int end) {
		this.end = end;
	}

	public int getEnd() {
		return end;
	}

	public int compareTo(Range r) {
		return compare(this, r);
	}
	
	/**
	 * Compare two ranges: use its begin attribute as the value.
	 * @param r1 the first range.
	 * @param r2 the second range.
	 * @return r1.begin-r2.begin
	 */
	public static int compare(Range r1, Range r2) {
		return r1.begin - r2.begin;
	}
	
	/**
	 * Join a Range with an two-dimension Range array.
	 * @param r Range object.
	 * @param ranges two-dimension Range array.
	 * @return r * [(r1, r2), (r3, r4)...] => [(r, r1, r2), (r, r3, r4)...]
	 */
	public static List<ArrayDeque<Range>> joinRanges(Range r, 
			List<ArrayDeque<Range>> ranges) {
		for(ArrayDeque<Range> q : ranges) {
			q.addFirst(r);
		}
		
		return ranges;
	}
	
	/**
	 * Get ranges that is bigger than object range, but not intersected.
	 * @param ranges A range list.
	 * @param range The object range.
	 * @return "Bigger" but not intersected ranges.
	 */
	public static List<Range> getBiggerRanges(List<Range> ranges, Range range) {
		List<Range> biggerRanges = new ArrayList<Range>();
		for(Range r : ranges) {
			if(r.begin > range.end)
				biggerRanges.add(r);
		}
		
		return biggerRanges;
	}
	
	/**
	 * To determine if a range object is in a two-dimension range array.
	 * @param r A range object.
	 * @param rangeLists Two dimension range array.
	 * @return True if the range object is in range array, else False.
	 */
	public static boolean inRangeLists(Range r, List<ArrayDeque<Range>> rangeLists) {
		for(ArrayDeque<Range> q : rangeLists) {
			if(q.contains(r)) {
				return true;
			}
		}
		return false;
	}
	
	/**
	 * Get longest range lists, the is the core algorithm to parse passwords.
	 * @param rangeList A range list.
	 * @return Longest range lists.
	 */
	public static List<ArrayDeque<Range>> longestRanges(List<Range> rangeList) {
		List<ArrayDeque<Range>> rangeLists = new ArrayList<ArrayDeque<Range>>();
		if(rangeList.size() == 0) {
			ArrayDeque<Range> q = new ArrayDeque<Range>();
			rangeLists.add(q);
			return rangeLists;
		}
		
		for(Range r : rangeList) {
			if(!inRangeLists(r, rangeLists)) {
				List<Range> ranges = getBiggerRanges(rangeList, r);
				rangeLists.addAll(joinRanges(r, longestRanges(ranges)));
			}
		}
		
		return rangeLists;
	}
}

class RangeException extends RuntimeException {
	private static final long serialVersionUID = 1L;
	
	private int begin, end;
	
	public RangeException(int begin, int end) {
		super();
		this.begin = begin;
		this.end = end;
	}
	
	@Override
	public String toString() {
		return String.format("Error range: (%d, %d)", this.begin, this.end);
	}
}